{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Evaluate Division"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph #array #shortest-path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图 #数组 #最短路"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: calcEquation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #除法求值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个变量对数组 <code>equations</code> 和一个实数值数组 <code>values</code> 作为已知条件，其中 <code>equations[i] = [A<sub>i</sub>, B<sub>i</sub>]</code> 和 <code>values[i]</code> 共同表示等式 <code>A<sub>i</sub> / B<sub>i</sub> = values[i]</code> 。每个 <code>A<sub>i</sub></code> 或 <code>B<sub>i</sub></code> 是一个表示单个变量的字符串。</p>\n",
    "\n",
    "<p>另有一些以数组 <code>queries</code> 表示的问题，其中 <code>queries[j] = [C<sub>j</sub>, D<sub>j</sub>]</code> 表示第 <code>j</code> 个问题，请你根据已知条件找出 <code>C<sub>j</sub> / D<sub>j</sub> = ?</code> 的结果作为答案。</p>\n",
    "\n",
    "<p>返回 <strong>所有问题的答案</strong> 。如果存在某个无法确定的答案，则用 <code>-1.0</code> 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 <code>-1.0</code> 替代这个答案。</p>\n",
    "\n",
    "<p><strong>注意：</strong>输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。</p>\n",
    "\n",
    "<p><strong>注意：</strong>未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>equations = [[\"a\",\"b\"],[\"b\",\"c\"]], values = [2.0,3.0], queries = [[\"a\",\"c\"],[\"b\",\"a\"],[\"a\",\"e\"],[\"a\",\"a\"],[\"x\",\"x\"]]\n",
    "<strong>输出：</strong>[6.00000,0.50000,-1.00000,1.00000,-1.00000]\n",
    "<strong>解释：</strong>\n",
    "条件：<em>a / b = 2.0</em>, <em>b / c = 3.0</em>\n",
    "问题：<em>a / c = ?</em>, <em>b / a = ?</em>, <em>a / e = ?</em>, <em>a / a = ?</em>, <em>x / x = ?</em>\n",
    "结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]\n",
    "注意：x 是未定义的 =&gt; -1.0</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>equations = [[\"a\",\"b\"],[\"b\",\"c\"],[\"bc\",\"cd\"]], values = [1.5,2.5,5.0], queries = [[\"a\",\"c\"],[\"c\",\"b\"],[\"bc\",\"cd\"],[\"cd\",\"bc\"]]\n",
    "<strong>输出：</strong>[3.75000,0.40000,5.00000,0.20000]\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>equations = [[\"a\",\"b\"]], values = [0.5], queries = [[\"a\",\"b\"],[\"b\",\"a\"],[\"a\",\"c\"],[\"x\",\"y\"]]\n",
    "<strong>输出：</strong>[0.50000,2.00000,-1.00000,-1.00000]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= equations.length &lt;= 20</code></li>\n",
    "\t<li><code>equations[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= A<sub>i</sub>.length, B<sub>i</sub>.length &lt;= 5</code></li>\n",
    "\t<li><code>values.length == equations.length</code></li>\n",
    "\t<li><code>0.0 &lt; values[i] &lt;= 20.0</code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 20</code></li>\n",
    "\t<li><code>queries[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= C<sub>j</sub>.length, D<sub>j</sub>.length &lt;= 5</code></li>\n",
    "\t<li><code>A<sub>i</sub>, B<sub>i</sub>, C<sub>j</sub>, D<sub>j</sub></code> 由小写英文字母与数字组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [evaluate-division](https://leetcode.cn/problems/evaluate-division/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [evaluate-division](https://leetcode.cn/problems/evaluate-division/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"a\",\"b\"],[\"b\",\"c\"]]\\n[2.0,3.0]\\n[[\"a\",\"c\"],[\"b\",\"a\"],[\"a\",\"e\"],[\"a\",\"a\"],[\"x\",\"x\"]]', '[[\"a\",\"b\"],[\"b\",\"c\"],[\"bc\",\"cd\"]]\\n[1.5,2.5,5.0]\\n[[\"a\",\"c\"],[\"c\",\"b\"],[\"bc\",\"cd\"],[\"cd\",\"bc\"]]', '[[\"a\",\"b\"]]\\n[0.5]\\n[[\"a\",\"b\"],[\"b\",\"a\"],[\"a\",\"c\"],[\"x\",\"y\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,own,target,hashmap,visited):\n",
    "        if target in hashmap[own]:\n",
    "            return hashmap[own][target]\n",
    "        \n",
    "        for i in hashmap[own].keys():\n",
    "            if i in visited:\n",
    "                continue\n",
    "            res = hashmap[own][i]\n",
    "            visited.add(i)\n",
    "            dfs_res = self.dfs(i,target,hashmap,visited)\n",
    "            if dfs_res != 0:\n",
    "                res = res * dfs_res\n",
    "                return res\n",
    "            \n",
    "        return 0\n",
    "             \n",
    "        \n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        hashmap = {}\n",
    "        for index, item in enumerate(equations):    \n",
    "            cur_fir = item[0]\n",
    "            cur_sec = item[1]\n",
    "            if cur_fir in hashmap:\n",
    "                hashmap[cur_fir][cur_sec] = values[index]\n",
    "            else:\n",
    "                hashmap[cur_fir] = {}\n",
    "                hashmap[cur_fir][cur_sec] = values[index]\n",
    "                \n",
    "            if cur_sec in hashmap:\n",
    "                hashmap[cur_sec][cur_fir] = 1/(values[index])\n",
    "            else:\n",
    "                hashmap[cur_sec] = {}\n",
    "                hashmap[cur_sec][cur_fir] = 1/(values[index])\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        for i in queries:\n",
    "            if i[0] not in hashmap or i[-1] not in hashmap:\n",
    "                res.append(float(-1))\n",
    "            else: #i[0] and i[1] both in hashmap\n",
    "                if i[1] in hashmap[i[0]]:\n",
    "                    res.append(float(hashmap[i[0]][i[1]]))\n",
    "                else:\n",
    "                    ret = self.dfs(i[0],i[1],hashmap,set())\n",
    "                    if ret != 0:\n",
    "                        res.append(float(ret))\n",
    "                    else:\n",
    "                        res.append(float(-1))\n",
    "        \n",
    "        \n",
    "        return res\n",
    "    \n",
    "        \n",
    "                \n",
    "            \n",
    "                \n",
    "            \n",
    "                \n",
    "         \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations, values, queries):\n",
    "        \"\"\"\n",
    "        :type equations: List[List[str]]\n",
    "        :type values: List[float]\n",
    "        :type queries: List[List[str]]\n",
    "        :rtype: List[float]\n",
    "        \"\"\"\n",
    "        eqMap = {} # key -> parent val -> set(child)\n",
    "        eqVal = {} # key -> (parent, child) val -> values\n",
    "        elementSet = set()\n",
    "        \n",
    "        for i in range(len(equations)):\n",
    "            elementSet.add(equations[i][0])\n",
    "            elementSet.add(equations[i][1])\n",
    "            eqVal[(equations[i][0], equations[i][1])] = values[i]\n",
    "            eqVal[(equations[i][1], equations[i][0])] = 1.0 / values[i]\n",
    "            if equations[i][0] not in eqMap:\n",
    "                 eqMap[equations[i][0]] = set()\n",
    "            eqMap[equations[i][0]].add(equations[i][1])\n",
    "            \n",
    "            if equations[i][1] not in eqMap:\n",
    "                 eqMap[equations[i][1]] = set()\n",
    "            eqMap[equations[i][1]].add(equations[i][0])\n",
    "        \n",
    "        result = []\n",
    "        \n",
    "        for query in queries:\n",
    "            if query[0] not in elementSet or query[1] not in elementSet:\n",
    "                result.append(-1.0)\n",
    "                continue\n",
    "            visited = set()\n",
    "            # dfs\n",
    "            stack = [[query[0], 1.0]]\n",
    "            flag = False\n",
    "            while stack:\n",
    "                current = stack.pop(-1)\n",
    "                visited.add(current[0])\n",
    "                if current[0] == query[1]:\n",
    "                    result.append(current[1])\n",
    "                    flag = True\n",
    "                    break\n",
    "                \n",
    "                if current[0] not in eqMap:\n",
    "                    break\n",
    "                # add candidates \n",
    "                for child in eqMap[current[0]]:\n",
    "                    if child not in visited:\n",
    "                        stack.append([child, current[1] * eqVal[(current[0], child)]])\n",
    "            if not flag:\n",
    "                result.append(-1.0)\n",
    "        return result\n",
    "                    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations, values, queries):\n",
    "        \"\"\"\n",
    "        :type equations: List[List[str]]\n",
    "        :type values: List[float]\n",
    "        :type queries: List[List[str]]\n",
    "        :rtype: List[float]\n",
    "        \"\"\"\n",
    "        d = {}\n",
    "        res = []\n",
    "        for i in range(len(equations)):\n",
    "            e, v = equations[i], values[i]\n",
    "            x, y = e\n",
    "            if x not in d:\n",
    "                d[x] = [(x, 1.0)]\n",
    "            if y not in d:\n",
    "                d[y] = [(y, 1.0)]\n",
    "            d[x].append((y, v))\n",
    "            d[y].append((x, 1.0 / v))\n",
    "        \n",
    "        def dfs(x, y, r, visited):\n",
    "            if x not in d or y not in d:\n",
    "                return -1.0, False\n",
    "            if x == y:\n",
    "                return r, True\n",
    "            visited.add(x)\n",
    "            for c, p in d[x]:\n",
    "                if c not in visited:\n",
    "                    newr, found = dfs(c, y, p * r, visited)\n",
    "                    if found:\n",
    "                        return newr, True\n",
    "            return -1.0, False\n",
    "        \n",
    "        for x, y in queries:\n",
    "            res.append(dfs(x, y, 1.0, set())[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations, values, queries):\n",
    "        \"\"\"\n",
    "        :type equations: List[List[str]]\n",
    "        :type values: List[float]\n",
    "        :type queries: List[List[str]]\n",
    "        :rtype: List[float]\n",
    "        \"\"\"\n",
    "        def dfs(key, version, value = float(1)):\n",
    "            refer[key] = [value, version]\n",
    "            for nei in dicti[key]:\n",
    "                if nei[0] not in refer:\n",
    "                    dfs(nei[0], version, refer[key][0] * nei[1])\n",
    "            \n",
    "        dicti, refer = collections.defaultdict(list), {}\n",
    "        for e, v in zip(equations, values):\n",
    "            dicti[e[1]].append([e[0], v])\n",
    "            dicti[e[0]].append([e[1], 1 / v])\n",
    "        cur = 1\n",
    "        for k in sorted(dicti.keys()):\n",
    "            if k not in refer:\n",
    "                dfs(k, cur)\n",
    "                cur += 1\n",
    "        print(refer)\n",
    "        return [refer[i][0] / refer[j][0] if i in refer and j in refer and refer[i][1] == refer[j][1] else float(-1) for i, j in queries]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations, values, queries):\n",
    "        \"\"\"\n",
    "        :type equations: List[List[str]]\n",
    "        :type values: List[float]\n",
    "        :type queries: List[List[str]]\n",
    "        :rtype: List[float]\n",
    "        \"\"\"\n",
    "        # 有向图 \n",
    "        # (a->b)=2 (b->a)=1/2 (a->c)=(a->b)+(b->c)\n",
    "        # 建立字典 储存左右相连的点\n",
    "        # DFS/BFS找到一点到零一点的路径\n",
    "        \n",
    "        dic = {}\n",
    "        for i in range(len(equations)):\n",
    "            if equations[i][0] not in dic:\n",
    "                dic[equations[i][0]] = [(equations[i][0], 1)]\n",
    "                dic[equations[i][0]].append((equations[i][1], values[i]))\n",
    "            else:\n",
    "                dic[equations[i][0]].append((equations[i][1], values[i]))\n",
    "            if equations[i][1] not in dic:\n",
    "                dic[equations[i][1]] = [(equations[i][1], 1)]\n",
    "                dic[equations[i][1]].append((equations[i][0], 1/values[i]))\n",
    "            else:\n",
    "                dic[equations[i][1]].append((equations[i][0], 1/values[i]))\n",
    "\n",
    "        \n",
    "        r = []\n",
    "        dic_r = {}\n",
    "        for i in queries:\n",
    "            r1 = self.DFS(dic, set(), i[0], i[1], dic_r)\n",
    "            if r1:\n",
    "                r.append(r1)\n",
    "            else:\n",
    "                r.append(-1)\n",
    "\n",
    "        return r\n",
    "        \n",
    "    \n",
    "    # dic_r相当于是邻接矩阵\n",
    "    def DFS(self, dic, used, start, target, dic_r):\n",
    "\n",
    "        if start not in dic:\n",
    "            return False\n",
    "        \n",
    "        if (start, target) in dic_r:\n",
    "            return dic_r[(start, target)]\n",
    "        \n",
    "        used.add(start)\n",
    "        for i in dic[start][1:]:  # dic[start][0]==start\n",
    "            \n",
    "            if i[0]==target:\n",
    "                dic_r[(start, target)] = i[1]\n",
    "                return i[1]\n",
    "            \n",
    "            if i[0] not in used:\n",
    "                res = self.DFS(dic, used, i[0], target ,dic_r)\n",
    "                if res:\n",
    "                    if (start, target) not in dic_r:\n",
    "                        dic_r[(start, target)] = i[1] * res\n",
    "                    return i[1] * res\n",
    "                \n",
    "        dic_r[(start, target)] = None\n",
    "        \n",
    "        return False\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        def dfs(start, end, vt):\n",
    "            if start not in graph and end not in graph:\n",
    "                return 0\n",
    "            if (start, end) in wgt:\n",
    "                return wgt[(start, end)]\n",
    "            vt.add(start)\n",
    "            res = 0\n",
    "            for t in graph[start]:\n",
    "                if t not in vt:\n",
    "                    res = dfs(t, end, vt) * wgt[(start, t)]\n",
    "                    if res:\n",
    "                        wgt[(start, end)] = res\n",
    "                        break\n",
    "            vt.remove(start)\n",
    "            return res\n",
    "        if not equations:\n",
    "            return []\n",
    "        n = len(equations)\n",
    "        import collections\n",
    "        graph = collections.defaultdict(set)\n",
    "        wgt = collections.defaultdict()\n",
    "        for i in range(n):\n",
    "            eq = equations[i]\n",
    "            graph[eq[0]].add(eq[1])\n",
    "            graph[eq[1]].add(eq[0])\n",
    "            wgt[(eq[0], eq[1])] = values[i]\n",
    "            wgt[(eq[1], eq[0])] = 1.0 / values[i]\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            t = dfs(q[0], q[1], set())\n",
    "            res.append(t if t else -1.0)\n",
    "        return res\n",
    "print(Solution().calcEquation([[\"x1\",\"x2\"],[\"x2\",\"x3\"],[\"x3\",\"x4\"],[\"x4\",\"x5\"]], [3.0,4.0,5.0,6.0], [['x2', 'x4']]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        g={}\n",
    "\n",
    "        for eq,val in zip(equations, values):\n",
    "            a,b=eq\n",
    "            if a not in g:\n",
    "                g[a]={b:val}\n",
    "            else :\n",
    "                g[a][b]=val\n",
    "            \n",
    "            if b not in g:\n",
    "                g[b]={a:1/val}\n",
    "            else:\n",
    "                g[b][a]=1/val\n",
    "        \n",
    "        self.g=g\n",
    "        self.result=[]\n",
    "        for q in queries:\n",
    "            self.begin,self.end=q\n",
    "            if self.begin not in self.g  or self.end  not in self.g:\n",
    "                self.result.append(-1.0)\n",
    "            elif self.begin==self.end:\n",
    "                self.result.append(1.0)\n",
    "            else:\n",
    "                self.flag=False\n",
    "                self.visited={}\n",
    "                self.dfs(self.begin,1)\n",
    "                if  self.flag is False:\n",
    "                    self.result.append(-1.)\n",
    "        return  self.result\n",
    "            \n",
    "\n",
    "    def dfs(self, cur, pre):\n",
    "        self.visited[cur]=1\n",
    "        neibor=self.g.get(cur,[])\n",
    "        for n in neibor:\n",
    "            if n==self.end:\n",
    "                self.flag=True\n",
    "                self.result.append(pre*self.g[cur][n])\n",
    "                return\n",
    "            if n not in self.visited:\n",
    "                self.dfs(n, pre*self.g[cur][n])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        def bfs(start,end):\n",
    "            q=deque([])\n",
    "            seen=set()\n",
    "            q.append((start,1))\n",
    "            seen.add(start)\n",
    "            while q:\n",
    "                node,res=q.popleft()\n",
    "                if node==end:\n",
    "                    #print(res)\n",
    "                    return res\n",
    "                for nextNode,weight in edges[node]:\n",
    "                    if nextNode  not in  seen:\n",
    "                        q.append((nextNode,res*weight))\n",
    "                        seen.add(nextNode)\n",
    "                #print(q)\n",
    "            return -1\n",
    "\n",
    "        from collections import deque\n",
    "        from collections import defaultdict\n",
    "        n=len(equations)\n",
    "        edges=defaultdict(set)\n",
    "        for i in range(0,len(equations)):\n",
    "            edges[equations[i][0]].add((equations[i][1],values[i]))\n",
    "            edges[equations[i][1]].add((equations[i][0],1/values[i]))\n",
    "        print(edges)\n",
    "        ans=[]\n",
    "        for q in queries:\n",
    "            start=q[0]\n",
    "            end=q[1]\n",
    "\n",
    "            #print(start,end)\n",
    "            if start in edges and end in edges:\n",
    "                res=bfs(start,end)\n",
    "            else:\n",
    "                res=-1\n",
    "\n",
    "            #print(res)\n",
    "            ans.append(res)\n",
    "        #print(ans)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.val = 1\n",
    "        self.father = self\n",
    "\n",
    "# 并查集的查找\n",
    "def find(node):\n",
    "    r = node\n",
    "    while r.father != r:\n",
    "        r = r.father\n",
    "\n",
    "    # 压缩路径\n",
    "    while node.father != node:\n",
    "        next_node =node.father\n",
    "        node.father =r\n",
    "        node = next_node\n",
    "    return r\n",
    "\n",
    "# 并查集的合并\n",
    "def union(node1, node2, val, child_dict):\n",
    "    # 祖先相同则不压缩\n",
    "    root1 = find(node1)\n",
    "    root2 = find(node2)\n",
    "    if root1 == root2:\n",
    "        return\n",
    "    \n",
    "    # 否则将父节点1的父节点从自身变为父节点2\n",
    "    # 此时需要将父节点1的集合都进行数值变化由于点1是点2的val倍，所以集合1都需要扩充node2.val * val / node1.val倍，即将点1的值变换为点2的val倍，其他的数进行相同倍数的变化\n",
    "    change_mul = node2.val * val / node1.val\n",
    "\n",
    "    # 这里使用了一个dict来保存每个祖先的子孙，以免重复查找\n",
    "    for node in child_dict[root1]:\n",
    "        node.val *= change_mul\n",
    "\n",
    "    root1.father = root2\n",
    "    child_dict[root2] += child_dict[root1]\n",
    "    child_dict.pop(root1)\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        str_node_dict = {}\n",
    "        child_dict ={}\n",
    "        for (x,y),v in zip(equations,values):\n",
    "            # 找到或创建其对应节点\n",
    "            if x in str_node_dict:\n",
    "                node1 = str_node_dict[x]\n",
    "            else:\n",
    "                node1 = Node()\n",
    "                str_node_dict[x] = node1\n",
    "                child_dict[node1] = [node1]\n",
    "            if y in str_node_dict:\n",
    "                node2 = str_node_dict[y]\n",
    "            else:\n",
    "                node2 = Node()\n",
    "                str_node_dict[y] = node2\n",
    "                child_dict[node2] = [node2]\n",
    "            \n",
    "            union(node1,node2,v,child_dict)\n",
    "    \n",
    "        res = []\n",
    "        for  x,y in queries:\n",
    "            if x not in str_node_dict or y not in str_node_dict:\n",
    "                res.append(-1.0)\n",
    "            elif find(str_node_dict[x]) != find(str_node_dict[y]):\n",
    "                res.append(-1.0)\n",
    "            else:\n",
    "                res.append(str_node_dict[x].val/str_node_dict[y].val)\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        d = dict()\n",
    "        for i,e in enumerate(equations):\n",
    "            a,b = e\n",
    "            if a not in d:\n",
    "                d[a] = dict()\n",
    "            if b not in d:\n",
    "                d[b] = dict()\n",
    "            d[a][b] = values[i]\n",
    "            d[b][a] = 1/values[i]\n",
    "        \n",
    "        rtv = []\n",
    "        for a,b in queries:\n",
    "            if a not in d or b not in d:\n",
    "                rtv.append(-1)\n",
    "                continue\n",
    "            todo = []\n",
    "            todo.append(a)\n",
    "            seen = set()\n",
    "            while todo:\n",
    "                cur = todo.pop(0)   #   BFS\n",
    "                if cur in seen:\n",
    "                    continue\n",
    "                seen.add(cur)\n",
    "                for ne in d[cur].keys():\n",
    "                    if ne not in d[a].keys():\n",
    "                        t = d[a][cur] * d[cur][ne]\n",
    "                        d[a][ne] = t\n",
    "                        d[ne][a] = 1/t\n",
    "                    if ne == b:\n",
    "                        todo = []\n",
    "                        break\n",
    "                    todo.append(ne)\n",
    "            if b not in d[a].keys():\n",
    "                rtv.append(-1)\n",
    "            else:\n",
    "                rtv.append(d[a][b])\n",
    "        return rtv\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        if not queries:\n",
    "            return []\n",
    "        if not equations or not values:\n",
    "            return [-1.0]*len(queries)\n",
    "        d = collections.defaultdict(dict)\n",
    "        for (a, b), val in zip(equations, values):\n",
    "            d[a][a] = d[b][b] = 1.0\n",
    "            d[a][b] = val\n",
    "            d[b][a] = 1/val\n",
    "        \n",
    "        for k in d:\n",
    "            for i in d[k]:\n",
    "                for j in d[k]:\n",
    "                    d[i][j] = d[i][k] * d[k][j]\n",
    "        return [d[a].get(b, -1.0) for a, b in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        d = {}\n",
    "        for i in range(len(equations)):\n",
    "            d[(equations[i][0], equations[i][1])] = values[i]\n",
    "\n",
    "        graph = collections.defaultdict(set)\n",
    "        v = {}\n",
    "        for index, equ in enumerate(equations):\n",
    "            graph[equ[0]].add(equ[1])\n",
    "            graph[equ[1]].add(equ[0])\n",
    "            v[(equ[0], equ[1])] = values[index]\n",
    "            v[(equ[1], equ[0])] = float(1 / values[index])\n",
    "\n",
    "        visited = set()\n",
    "        # def dfs(start, end):\n",
    "        #     nonlocal visited\n",
    "        #     if start in visited:    return 0\n",
    "        #     if (start, end) in v:   return v[(start, end)]\n",
    "        #     if start not in graph or end not in graph:    return 0\n",
    "        #     visited.add(start)\n",
    "        #     for neighbor in graph[start]:\n",
    "        #         temp = dfs(neighbor, end) * v[(start, neighbor)]\n",
    "        #         if temp != 0: \n",
    "        #             visited.remove(start)\n",
    "        #             v[(start, end)] = temp\n",
    "        #             v[(end, start)] = float(1 / temp)\n",
    "        #             return temp\n",
    "        #     visited.remove(start)\n",
    "        #     return 0\n",
    "\n",
    "        def dfs(start, end):\n",
    "            nonlocal visited\n",
    "            if start not in graph or end not in graph:  return 0\n",
    "            if start == end:    return 1.0\n",
    "            if start in visited:    return 0\n",
    "            if (start, end) in v:   return v[(start, end)]\n",
    "            visited.add(start)\n",
    "            for neighbor in graph[start]:\n",
    "                temp_res = dfs(neighbor, end) * v[(start, neighbor)]\n",
    "                if temp_res: \n",
    "                    v[(start, end)] = temp_res\n",
    "                    v[(end, start)] = float(1 / temp_res)\n",
    "                    break\n",
    "            visited.remove(start)\n",
    "            return temp_res\n",
    "\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            vq = dfs(q[0], q[1])\n",
    "            res.append(float(vq) if vq != 0 else -1.0) \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        \n",
    "        d = collections.defaultdict(dict)\n",
    "        for (a, b), val in zip(equations, values):\n",
    "            d[a][a] = d[b][b] = 1.0\n",
    "            d[a][b] = val\n",
    "            d[b][a] = 1/val\n",
    "        \n",
    "        for k in d:\n",
    "            for i in d[k]:\n",
    "                for j in d[k]:\n",
    "                    d[i][j] = d[i][k] * d[k][j]\n",
    "        return [d[num].get(den, -1.0) for num, den in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        eqdic={}\n",
    "        for (a,b),c in zip(equations,values):\n",
    "            if a in eqdic:\n",
    "                eqdic[a][b]=c\n",
    "            else:\n",
    "                eqdic[a]={b:c}\n",
    "            if b in eqdic:\n",
    "                eqdic[b][a]=1.0/c\n",
    "            else:\n",
    "                eqdic[b]={a:1.0/c}\n",
    "        vis={}\n",
    "        for v in eqdic:\n",
    "            vis[v]=False\n",
    "        def serach(dic,visited,l,r,base):\n",
    "            if l not in visited or r not in visited:\n",
    "                return -1.0\n",
    "            else:\n",
    "                for t in dic[l]:\n",
    "                    if not visited[t]:\n",
    "                        if  t==r:\n",
    "                            return base*dic[l][r]\n",
    "                        else:\n",
    "                            visited[t]=True\n",
    "                            s=serach(dic,visited,t,r,base*dic[l][t])\n",
    "                            visited[t]=False\n",
    "                            if s==-1:\n",
    "                                continue\n",
    "                            else:\n",
    "                                return s\n",
    "                return -1\n",
    "        res=[]\n",
    "        for x,y in queries:\n",
    "            res.append(serach(eqdic,vis,x,y,1))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        # 路径压缩\n",
    "        connect_dic = {}\n",
    "        weight_dic = {}\n",
    "\n",
    "        def add(val):\n",
    "            if val not in connect_dic:\n",
    "                connect_dic[val] = val\n",
    "                weight_dic[val] = (1, val)\n",
    "\n",
    "        def union(val1, val2, weight):\n",
    "            val1_children = find_children(val1)\n",
    "            val2_children = find_children(val2)\n",
    "            if val1_children != val2_children:\n",
    "                val1_weight = find_weight(val1)\n",
    "                val2_weight = find_weight(val2)\n",
    "                connect_dic[val1_children] = val2_children\n",
    "                weight_dic[val1_children] = (weight * (val2_weight / val1_weight), val2_children)\n",
    "\n",
    "        def find_children(val):\n",
    "            if connect_dic[val] != val:\n",
    "                connect_dic[val] = find_children(connect_dic[val])\n",
    "            return connect_dic[val]\n",
    "\n",
    "        def find_weight(val):\n",
    "            true_children = find_children(val)\n",
    "            weight, v = weight_dic[val]\n",
    "            while v != true_children:\n",
    "                w, v = weight_dic[v]\n",
    "                weight *= w\n",
    "            return weight\n",
    "\n",
    "        for (val1, val2), weight in zip(equations, values):\n",
    "            add(val1)\n",
    "            add(val2)\n",
    "            union(val1, val2, weight)\n",
    "\n",
    "        res = []\n",
    "        for val1, val2 in queries:\n",
    "            if val1 in connect_dic and val2 in connect_dic and find_children(val1) == find_children(val2):\n",
    "                val1_weight = find_weight(val1)\n",
    "                val2_weight = find_weight(val2)\n",
    "                res.append(val1_weight / val2_weight)\n",
    "            else:\n",
    "                res.append(-1.0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        from collections import defaultdict\n",
    "        node = []\n",
    "        for i in range(len(equations)):\n",
    "            node.append(equations[i][0])\n",
    "            node.append(equations[i][1])\n",
    "        node = list(set(node))\n",
    "        path = defaultdict(lambda: defaultdict(lambda: -1))\n",
    "        for i in range(len(equations)):\n",
    "            path[equations[i][0]][equations[i][1]] = float(values[i])\n",
    "            path[equations[i][0]][equations[i][0]] = 1\n",
    "            path[equations[i][1]][equations[i][1]] = 1\n",
    "            if(values[i] - 0.0 < 0.0000001):\n",
    "                path[equations[i][1]][equations[i][0]] = -1\n",
    "            else:\n",
    "                path[equations[i][1]][equations[i][0]] = float(1.0) / float(values[i])\n",
    "            # print(values[i])\n",
    "        res = []\n",
    "        # for i in range(len(node)):\n",
    "            # for j in range(len(node)):\n",
    "                # if(path[node[i]][node[j]] != -1):\n",
    "                    # print(n(no, node[j], path[node[i]][node[j]])\n",
    "        for i in range(len(queries)):\n",
    "            st = queries[i][0]\n",
    "            ed = queries[i][1]\n",
    "            if(st not in node):\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            if(path[st][ed] != -1):\n",
    "                res.append(path[st][ed])\n",
    "                continue\n",
    "            queue = [st]\n",
    "            # cur_res = 1.0\n",
    "            # print(st, ed, \"----------\")\n",
    "            vis = defaultdict(int)\n",
    "            vis[st] = 1\n",
    "            while(queue):\n",
    "                vis[queue[0]] = 1\n",
    "                if(queue[0] == ed):\n",
    "                    # flag = 1\n",
    "                    res.append(path[st][ed])\n",
    "                    break\n",
    "                for j in range(len(node)):\n",
    "                    if(vis[node[j]] == 0):\n",
    "                        if(path[queue[0]][node[j]] != -1):\n",
    "                            queue.append(node[j])\n",
    "                            vis[node[j]] = 1\n",
    "                            path[st][node[j]] = path[st][queue[0]] * path[queue[0]][node[j]]\n",
    "                            path[node[j]][st] = path[queue[0]][st] * path[node[j]][queue[0]]\n",
    "                        # print(cur_res, queue[0], node[j])\n",
    "                        # flag = 1\n",
    "                queue = queue[1:]\n",
    "            if(vis[ed] == 0):\n",
    "                res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        graph = {}\n",
    "        for idx in range(len(equations)):\n",
    "            i, j = equations[idx]\n",
    "            if i not in graph:\n",
    "                graph[i] = {j: values[idx]}\n",
    "            else:\n",
    "                graph[i][j] = values[idx]\n",
    "            if j not in graph:\n",
    "                graph[j] = {i: 1 / values[idx]}\n",
    "            else:\n",
    "                graph[j][i] = 1 / values[idx]\n",
    "\n",
    "        ret = [-1.0 for i in range(len(queries))]\n",
    "\n",
    "        def dfs(i, j, val):\n",
    "            visited[i] = 1\n",
    "            if i not in graph:\n",
    "                return -1.0\n",
    "            if i == j:\n",
    "                return val\n",
    "            for nxt in graph[i]:\n",
    "                if not visited[nxt]:\n",
    "                    dfs_nxt = dfs(nxt, j, val * graph[i][nxt])\n",
    "                    if dfs_nxt != -1.0:\n",
    "                        return dfs_nxt\n",
    "            visited[i] = 0\n",
    "            return -1.0\n",
    "        \n",
    "        for idx in range(len(queries)):\n",
    "            i, j = queries[idx]\n",
    "            visited = {a: 0 for a in graph}\n",
    "            ret[idx] = dfs(i, j, 1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations, values, queries):\n",
    "\n",
    "        def UFS_find(father_dict,x):\n",
    "            temp=x\n",
    "            try:\n",
    "                while x!=father_dict[x]:\n",
    "                    x=father_dict[x]\n",
    "                \n",
    "                while temp!=father_dict[temp]:\n",
    "                    a=father_dict[temp]\n",
    "                    father_dict[temp]=x\n",
    "                    temp=a\n",
    "\n",
    "                return x\n",
    "            except:\n",
    "                return None  #出现未知字母\n",
    "\n",
    "        def UFS_union(father_dict,x,y):\n",
    "            father_x=UFS_find(father_dict,x)\n",
    "            father_y=UFS_find(father_dict,y)\n",
    "            father_dict[father_y]=father_x\n",
    "        \n",
    "        def DFS(graph,visit,start,target,express):\n",
    "            if break_flag[0]==True:\n",
    "                return\n",
    "            \n",
    "            express*=start[1]\n",
    "\n",
    "            if start[0]==target:\n",
    "                #express[0]*=start[1]\n",
    "                break_flag[0]=True\n",
    "                result[0]=express\n",
    "                print(\"result[0]=express\",express)\n",
    "                return express\n",
    "\n",
    "            print(\"express*=start[1]\",start[1])\n",
    "            visit[start[0]]=True\n",
    "            for node in graph[start[0]]:\n",
    "                if not visit[node[0]]:\n",
    "                    #express*=node[1]\n",
    "                    #visit[node[0]]=True\n",
    "                    DFS(graph,visit,node,target,express)\n",
    "                    #visit[node[0]]=False\n",
    "                    #express/=node[1]\n",
    "            visit[start[0]]=False\n",
    "            express/=start[1]\n",
    "            print(\"express/=tart[1]\",start[1])\n",
    "                    \n",
    "\n",
    "        computable_union={}\n",
    "        graph_neibor={}\n",
    "        variables=set([item[0] for item in equations] + [item[1] for item in equations])\n",
    "        print(variables)\n",
    "        #并查集初始化\n",
    "        \n",
    "        for var in variables:\n",
    "            computable_union[var]=var\n",
    "\n",
    "        for i in range(len(equations)):\n",
    "            equa=equations[i]\n",
    "            UFS_union(computable_union,equa[0],equa[1])\n",
    "            if graph_neibor.get(equa[0]):\n",
    "                graph_neibor[equa[0]].append((equa[1],values[i]))\n",
    "            else:\n",
    "                graph_neibor[equa[0]]=[(equa[1],values[i])]\n",
    "\n",
    "            if graph_neibor.get(equa[1]):\n",
    "                graph_neibor[equa[1]].append((equa[0],1/values[i]))\n",
    "            else:\n",
    "                graph_neibor[equa[1]]=[(equa[0],1/values[i])]            \n",
    "        \n",
    "        print(\"graph_neibor\",graph_neibor)\n",
    "        visit={}\n",
    "        for key in graph_neibor.keys():\n",
    "            visit[key]=False\n",
    "        \n",
    "        #python中的全局变量可以通过list的方式传进去\n",
    "\n",
    "\n",
    "        results=[]\n",
    "        for query in queries:\n",
    "        #query=queries[2]\n",
    "        #if True:\n",
    "            break_flag=[False]\n",
    "            result=[1]\n",
    "            if not computable_union.get(query[0]) or UFS_find(computable_union,query[0])!=UFS_find(computable_union,query[1]): \n",
    "                 results.append(-1)\n",
    "            else:\n",
    "                #visit[query[0]]=True\n",
    "                DFS(graph_neibor,visit,(query[0],1),query[1],1)\n",
    "                #visit[query[0]]=False\n",
    "                results.append(result[0])\n",
    "\n",
    "\n",
    "        print(results)\n",
    "        #print(visit)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        pool = []\n",
    "        edges = []\n",
    "        res = []\n",
    "        for i, equation in enumerate(equations):\n",
    "            pool.append(equation[0])\n",
    "            pool.append(equation[1])\n",
    "            edges.append((equation[0], equation[1], values[i]))\n",
    "            edges.append((equation[0], equation[0], 1.0))\n",
    "            edges.append((equation[1], equation[1], 1.0))\n",
    "            edges.append((equation[1], equation[0], 1.0 / values[i]))\n",
    "\n",
    "\n",
    "\n",
    "        print(edges)\n",
    "        for w,query in enumerate(queries):\n",
    "            a = query[0]\n",
    "            b = query[1]\n",
    "            # print(w,\"query\", a, b)\n",
    "            # if w==3:\n",
    "            #     return res\n",
    "            if a not in pool or b not in pool:\n",
    "                res.append(-1.0)\n",
    "                continue\n",
    "            if a == b:\n",
    "                res.append(1.0)\n",
    "                continue\n",
    "            q = []\n",
    "            for edge in edges:\n",
    "                if edge[0] == a:\n",
    "                    q.append((edge[1], edge[2]))\n",
    "            around = 0\n",
    "            flg = False\n",
    "            while(len(q)>0):\n",
    "                next_q = []\n",
    "                if flg:\n",
    "                    break\n",
    "                for i in range(len(q)):\n",
    "                    \n",
    "                    v, val = q.pop()\n",
    "                    if v == b:\n",
    "                        flg = True\n",
    "                        res.append(val)\n",
    "                        break\n",
    "                    else:\n",
    "                        for edge in edges:\n",
    "                            if edge[0] == v:\n",
    "                                next_q.append((edge[1], edge[2]*val))\n",
    "                    \n",
    "                around+=1\n",
    "                if around>len(edges)//4:\n",
    "                    flg = True\n",
    "                    res.append(-1.0)\n",
    "                    break\n",
    "                q = next_q\n",
    "        # print(res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        neighbors = defaultdict(set)\n",
    "        results = defaultdict(dict)\n",
    "        n = len(equations)\n",
    "        for i in range(n):\n",
    "            equ = equations[i]\n",
    "            a, b = equ[0], equ[1]\n",
    "            neighbors[a].add(b)\n",
    "            neighbors[b].add(a)\n",
    "            results[a][b] = values[i]\n",
    "            results[b][a] = 1 / values[i]\n",
    "\n",
    "        def bfs(start, end):\n",
    "            if start not in neighbors:\n",
    "                return -1.0\n",
    "            q = deque([(start, 1)])\n",
    "            seen = set()\n",
    "            while q:\n",
    "                node, v = q.popleft()\n",
    "                if node == end:\n",
    "                    return v\n",
    "                for x in neighbors[node]:\n",
    "                    if x not in seen:\n",
    "                        # v = start / node\n",
    "                        # k = node / x\n",
    "                        # start / x = v * k\n",
    "                        q.append((x, v * results[node][x]))\n",
    "                        seen.add(x)\n",
    "            return -1.0\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ans.append(bfs(q[0], q[1]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        p = list(range(128))\n",
    "        d = [1] * 128\n",
    "        n, map = 0, dict()\n",
    "        def get(x):\n",
    "            nonlocal n\n",
    "            if x not in map:\n",
    "                map[x] = n\n",
    "                n += 1\n",
    "            return map[x]\n",
    "        def find(x):\n",
    "            if x != p[x]:\n",
    "                root = find(p[x])\n",
    "                d[x] *= d[p[x]]\n",
    "                p[x] = root\n",
    "            return p[x]\n",
    "        for (x, y), value in zip(equations, values):\n",
    "            x, y = get(x), get(y)\n",
    "            px, py = find(x), find(y)\n",
    "            d[px] = value * d[y] / d[x]\n",
    "            p[px] = py\n",
    "        ans = []\n",
    "        for x, y in queries:\n",
    "            if x not in map or y not in map: \n",
    "                ans.append(-1)\n",
    "                continue\n",
    "            x, y = get(x), get(y)\n",
    "            px, py = find(x), find(y)\n",
    "            if px != py:\n",
    "                ans.append(-1.0)\n",
    "            else:\n",
    "                ans.append(d[x] / d[y])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        equation_size = len(equations)\n",
    "        union_find = UnionFind(2 * equation_size)\n",
    "        hash_map = {}\n",
    "        idx = 0\n",
    "        for i in range(equation_size):\n",
    "            equation = equations[i]\n",
    "            if equation[0] not in hash_map:\n",
    "                hash_map[equation[0]] = idx\n",
    "                idx += 1\n",
    "            if equation[1] not in hash_map:\n",
    "                hash_map[equation[1]] = idx\n",
    "                idx += 1\n",
    "            union_find.union(hash_map[equation[0]], hash_map[equation[1]], values[i])\n",
    "\n",
    "        queries_size = len(queries)\n",
    "        res = [0.] * queries_size\n",
    "\n",
    "        for i in range(queries_size):\n",
    "            var1 = queries[i][0]\n",
    "            var2 = queries[i][1]       \n",
    "            if var1 not in hash_map or var2 not in hash_map:\n",
    "                res[i] = -1.0\n",
    "            else:\n",
    "                res[i] = union_find.is_connected(hash_map[var1], hash_map[var2])\n",
    "        return res\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [0] * n\n",
    "        self.weight = [0.] * n\n",
    "        for i in range(n):\n",
    "            self.parent[i] = i\n",
    "            self.weight[i] = 1.0\n",
    "\n",
    "    def union(self, x, y, value):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if (rootX == rootY):\n",
    "            return\n",
    "\n",
    "        self.parent[rootX] = rootY;\n",
    "        # 关系式的推导请见「参考代码」下方的示意图\n",
    "        self.weight[rootX] = self.weight[y] * value / self.weight[x];\n",
    "    \n",
    "    # 路径压缩\n",
    "    def find(self, x):\n",
    "        if (x != self.parent[x]):\n",
    "            origin = self.parent[x]\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "            self.weight[x] *= self.weight[origin]\n",
    "        return self.parent[x]\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if (rootX == rootY):\n",
    "            return self.weight[x] / self.weight[y]\n",
    "        else:\n",
    "            return -1.0"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
